package prog;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;


public class Kruskal {

    private Grafo G;
    private Integer w;
    List<ArestaKruskal> arestas;
    private List<ArestaKruskal> A;
    private List<Integer> p = new ArrayList<>();
    private List<Integer> rank = new ArrayList<>();

    public Kruskal(Grafo G, Integer w) {
        this.G = G;
        this.w = w;
    }

    public void executeKruskal() {

        arestas = new ArrayList<>();
        montaEstruturaArestas();

        A = new ArrayList<>();

        for (int i = 0; i < G.countVertices(); i++) {
            MakeSet(i);
        }

        for (ArestaKruskal aresta : arestas) {
            if (!(FindSet(aresta.u) == FindSet(aresta.v))) {
                A.add(aresta);
                Union(aresta.u, aresta.v);
            }
        }

      //  imprimeResultado();
    }

    private void MakeSet(Integer idVertice) {
        p.add(idVertice);
        rank.add(0);
    }

    private int FindSet(int x) {
        if (!(x == p.get(x))) {
            p.set(x, FindSet(p.get(x)));
        }
        return p.get(x);
    }

    private void Union(int x, int y) {
        Link(FindSet(x), FindSet(y));
    }

    private void Link(int x, int y) {
        if (rank.get(x) > rank.get(y)) {
            p.set(y, x);
        } else {
            p.set(x, y);
            if (rank.get(x) == rank.get(y)) {
                rank.set(y, rank.get(y) + 1);
            }
        }
    }

    private void montaEstruturaArestas() {
        //populando o ArrayList com todas as arestas
        for (int i = 0; i < G.countVertices(); i++) {
            for (int j = 0; j < G.getListaAdjacencias(i).getSize(); j++) {
                arestas.add(new ArestaKruskal(i, G.getListaAdjacencias(i).getAresta(j).getIdVertice(), Integer.parseInt(G.getListaAdjacencias(i).getAresta(j).getRotulo())));
            }
        }

        //ordenando o ArrayList de arestas
        Collections.sort(arestas, new Comparator<ArestaKruskal>() {
            @Override
            public int compare(ArestaKruskal a1, ArestaKruskal a2) {
                return a1.peso <= a2.peso ? -1 : (a1.peso > a2.peso ? +1 : 0);
            }
        });
    }

    public void imprimeResultado() {
        for (ArestaKruskal asd : A) {
            System.out.println(G.getRotuloVertice(asd.u) + " " + G.getRotuloVertice(asd.v));
        }
    }

    public List<ArestaKruskal> getA() {
        return A;
    }
    
}